package J3_20;

import java.util.*;

public class test {

    //给你一个下标从 0 开始的整数数组 nums 。
    //
    //如果一个前缀 nums[0..i] 满足对于 1 <= j <= i 的所有元素都有 nums[j] = nums[j - 1] + 1 ，那么我们称这个前缀是一个 顺序前缀 。特殊情况是，只包含 nums[0] 的前缀也是一个 顺序前缀 。
    //
    //请你返回 nums 中没有出现过的 最小 整数 x ，满足 x 大于等于 最长 顺序前缀的和。
    public static int missingInteger1(int[] nums) {
        if (nums.length == 1) {
            return nums[0] + 1;
        }
        Stack<Integer> queue = new Stack<>();
        queue.push(nums[0]);
        Set<Integer> set = new HashSet<>();
        set.add(nums[0]);
        int sum = 0;
        int max = 0;
        for (int i = 1; i < nums.length; i++) {
            set.add(nums[i]);
            if (nums[i] != queue.peek() + 1) {
                while (!queue.isEmpty()) {
                    sum += queue.pop();
                }
                max = Math.max(sum,max);
                sum = 0;
            }
            queue.push(nums[i]);
        }
        if (queue.size() == nums.length) {
            while (!queue.isEmpty()) {
                sum += queue.pop();
            }
            max = Math.max(sum,max);
        }
        while (set.contains(max)) {
            max++;
        }
        return max;
    }


    public int missingInteger(int[] nums) {
        if (nums.length == 1) {
            return nums[0] + 1;
        }
        int sum = nums[0];
        Set<Integer> set = new HashSet<>();
        boolean starSet = false;
        set.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (!starSet && nums[i] == nums[i - 1] + 1) {
                sum += nums[i];
            } else  {
                starSet = true;
            }
            set.add(nums[i]);
        }
        while (set.contains(sum)) {
            sum++;
        }
        return sum;

    }


    //给你一个正整数 p 。你有一个下标从 1 开始的数组 nums ，这个数组包含范围 [1, 2p - 1] 内所有整数的二进制形式（两端都 包含）。你可以进行以下操作 任意 次：
    //
    //从 nums 中选择两个元素 x 和 y  。
    //选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数 相同位置 的二进制位。
    //比方说，如果 x = 1101 且 y = 0011 ，交换右边数起第 2 位后，我们得到 x = 1111 和 y = 0001 。
    //
    //请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。将乘积对 109 + 7 取余 后返回。
    //
    //注意：答案应为取余 之前 的最小值。
    public static int minNonZeroProduct(int p) {
        if (p == 1) {
            return 1;
        }
        int mod = (int) (1e9 + 7);
        int x = fastPow(2,p,mod) - 1;
        int y = (x + 1) /2 - 1;
        return fastPow(x - 1, y, mod) * x % mod;
    }

    private static int fastPow(int i, int p, int mod) {
        int ret = 1;
        while (p != 0) {
            if ((p & 1) == 1) {
                ret =ret * i %mod;
            }
            i = i * i % mod;
            p >>= 1;
        }
        return ret;
    }

    //给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
    //
    //如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
    //
    //假设环境不允许存储 64 位整数（有符号或无符号）。
    public static int reverse(int x) {
        if (x < 0) {
            return -reverse(-x);
        }
        int res = 0;
        while (x != 0) {
            if (res > Integer.MAX_VALUE /10 || res < Integer.MIN_VALUE / 10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            res = res * 10 + digit;
        }
        return res;
    }



    public static void main(String[] args) {
        int s = reverse(-321);
        System.out.println(s);
    }
}
